package leetcode.code1289;

public class Solution2 {
	public int minFallingPathSum(int[][] grid) {
		int m = grid.length, n = grid[0].length;
		int f = 0, s = 0, p = -1;
		for (int i = 0; i < m; i++) {
			int ff = Integer.MAX_VALUE, ss = Integer.MAX_VALUE, pp = -1;
			for (int j = 0; j < n; j++) {
				int c = grid[i][j];
				if (j == p) {
					c += s;
				} else {
					c += f;
				}
				if (c < ff) {
					ss = ff;
					ff = c;
					pp = j;
				} else if (c < ss) {
					ss = c;
				}
			}
			f = ff;
			s = ss;
			p = pp;
		}
		return f;
	}
}
